“The great wall is made by blocks”

二进制加法

半加器

我们考虑最基本的二进制加法，两位相加，然后再扩展到高位上。对于一个对a, b两位相加的加法器，我们称其为半加器，输入是a, b两位，输出为和sum以及进位carry

图片名称

半加器实际上就是不考虑输入进位的加法器

全加器

现在我们考虑进位，引入全加器，即在输入端考虑有进位的情况，全加器的真值表如下：

c	b	a	sum(out)	carry(out)
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

实际上全加器就是计算( a + b + carry)，可以用两个半加器实现，实现方式如下：

图片名称

多位加法器

现在我们来考虑如何实现多位加法，一样的道理，对于每一位运算，我们可以使用一个全加器，对于第一位，输入的carry设置为0即可，也不难，这里来直接给出HDL实现

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/02/Adder16.hdl

/**
 * Adds two 16-bit values.
 * The most significant carry bit is ignored.
 */

CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    // Put you code here:
    HalfAdder(a = a[0], b = b[0],            sum = out[0],  carry = c0);    // The first bit not have a carry, use a half adder
    FullAdder(a = a[1], b = b[1],   c = c0,  sum = out[1],  carry = c1);
    FullAdder(a = a[2], b = b[2],   c = c1,  sum = out[2],  carry = c2);
    FullAdder(a = a[3], b = b[3],   c = c2,  sum = out[3],  carry = c3);

    FullAdder(a = a[4], b = b[4],   c = c3,  sum = out[4],  carry = c4);
    FullAdder(a = a[5], b = b[5],   c = c4,  sum = out[5],  carry = c5);
    FullAdder(a = a[6], b = b[6],   c = c5,  sum = out[6],  carry = c6);
    FullAdder(a = a[7], b = b[7],   c = c6,  sum = out[7],  carry = c7);

    FullAdder(a = a[8], b = b[8],   c = c7,  sum = out[8],  carry = c8);
    FullAdder(a = a[9], b = b[9],   c = c8,  sum = out[9],  carry = c9);
    FullAdder(a = a[10], b = b[10], c = c9,  sum = out[10], carry = c10);
    FullAdder(a = a[11], b = b[11], c = c10, sum = out[11], carry = c11);

    FullAdder(a = a[12], b = b[12], c = c11, sum = out[12], carry = c12);
    FullAdder(a = a[13], b = b[13], c = c12, sum = out[13], carry = c13);
    FullAdder(a = a[14], b = b[14], c = c13, sum = out[14], carry = c14);
    FullAdder(a = a[15], b = b[15], c = c14, sum = out[15], carry = c15);    // Omit the carry when do last bit add
}

这个加法器的一个问题是进位信号在16个门之间传递，效率比较低，有一种方法叫做carry look ahead，即超前进位加法器，优点是速度快，缺点是器件会增加很多：

图片名称

负数

如果我们用最高位表示符号，即可得到负数， $-x$ 可以使用如下公式进行计算：

$-(2^{n}-x)$

例如对于二进制1001 (9)，对应的负数为 $-(2^{4}-9) = (-7)$ ，我们称 $9$ 为 $-7$ 的补数，此处我们给出一个重要结论，两个负数相加可以表示为它们的补数相加：

$\begin{equation} \begin{aligned} -7+(-6)&=-(2^{4}-9) + (-(2^{4}-10))\\ &=9+10 \end{aligned} \end{equation}$

由于我们抛弃了最高位，因此得到的补数和所需的负数结果相同。现在我们需要考虑给定一个数 $x$ ，如何获取他的负数 $-x$ ？这样我们就可以将减法转化为加法： $y-x=y+(-x)$ 。即我们需要如下芯片：

$\textrm{Input}: x$

$\textrm{Output}: -x$

这里我们运用一个小技巧：为了计算 $(2^{n}-x)$ ，我们可以计算 $2^n-x=1+(2^{n}-1)-x$ ，这样做的好处是 $2^{n}-1$ 全部为1，做减法不需要借位，只需要将被减数按位翻转即可，所以这里我们得到了最终的结论，很重要，记住：一个负数等于其正数按位翻转后+1

算数逻辑单元（ALU）

现在我们来构造CPU中最重要的模块：ALU，其模块图如下所示：

图片名称

ALU：输入两个操作数和待执行的函数（算数或逻辑运算），给出指定结果，对于本课程的Hack ALU，其结构如下所示：

图片名称

根据六个输入控制位zx, nx, zy, ny, f, no，可以选择不同的操作，Hack ALU支持的操作如下：

输出立即数	一元逻辑运算	二元逻辑运算	数学运算
0	x	x & y	-x
1	y	x \	y	-y
-1	!x		x+1
	!y		y+1
			x-1
			y-1
			x+y
			x-y
			y-x

同时，该ALU还有两个输出控制位zr, ng，表示输出是否为0或者为负数，ALU的HDL代码框架如下：

Chip name: ALU
Inputs: x[16], y[16], // Two 16-bit data inputs
    // Your ALU should first deal with zx, then nx
    zx, // Zero the x input
    nx, // Negate the x input
    zy, // Zero the y input
    ny, // Negate the y input
    f, // Function code: 1 for Add, 0 for And
    no // Negate the out output
Outputs: out[16], // 16-bit output
    zr, // True iff out=0
    ng // True iff out<0
Function: if zx then x = 0 // 16-bit zero constant
          if nx then x = !x // Bit-wise negation
          if zy then y = 0 // 16-bit zero constant
          if ny then y = !y // Bit-wise negation
          if f then out = x + y // Integer 2's complement addition
               else out = x & y // Bit-wise And
          if no then out = !out // Bit-wise negation
          if out=0 then zr = 1 else zr = 0 // 16-bit eq. comparison
          if out<0 then ng = 1 else ng = 0 // 16-bit neg. comparison
Comment: Overflow is neither detected nor handled

控制位的真值表如下：

图片名称

我们解释一下其中几行比较迷惑的

计算1：为了计算1，我们可以对齐按位取反，得到b’1110，而b’1110为 $-2$ ，即 $-1+(-1)$ ，故只需要将 $x$ 与 $y$ 归零并按位取反即可
计算 $-x$ ： $-x=\overline x+1$ ，故 $-x-1=\overline x$ ，两边同时取反，可得 $\overline{-x-1}=x$ ，令 $x=-x$ ，即可得到 $\overline{x-1}=-x$ 。
计算 $x-y$ ：

$\begin{aligned} x-y&=-(\overline x+1)-y \\ &=-(\overline x+y)-1\\ -(\overline x+y) &=\overline{(\overline x+y)}+1\\ x-y&=\overline{\overline x+y} \end{aligned}$

参考文献

The Elements of Computing Systems (nand2tetris.org) ↩